package com.example.leetcode.StackSimple;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * Next Greater Element
 * num1是num2的子集
 * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
 * 输出: [3,-1]
 * 解释:
 *     对于num1中的数字2，第二个数组中的下一个较大数字是3。
 *     对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
 */
public class D_下一个更大元素 {
    public static void main(String[] args) {
        int[] nums1={4,1,2} ;
        int[] nums2={1,3,4,2};
        Solution solution = new Solution();
        System.out.println(solution.nextGreaterElement(nums1,nums2));
    }
}
/*
* 思路一: 遍历,遍历,再遍历
* */
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res=new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i]==nums2[j]) {
                    res[i]=-1;
                    for (int k = j; k < nums2.length; k++) {
                        if (nums2[k]>nums1[i]) {
                            res[i]=nums2[k];
                            break;
                        }
                    }
                    break;
                }
            }
        }
        return res;
    }
}

/**
 * 思路二:
 * map 记录nums2每个值的下一个更大元素 , 结果直接用map.get即可
 * 那么这个map如何构建出来呢
 * 先把nums2最后一个值作为key,值为-1放进map
 * 反向遍历num2 [倒数第二个值 --> 0] 遍历过程中, 如果i+1的值比i的大,说明这是i+1是i的 下一个更大元素,则put进map
 * 否则,则开始寻找Map,Map本身没有规律可以遵循,但是由于构建的map的是key为num2里面的值,value是其下一个更大元素,
 * 遵从这个规律找 i的下一个更大元素
 *
 */
class Solution2 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0){
            return new int[0];
        }
        Map<Integer, Integer> map  = new HashMap<>();
        map.put(nums2[nums2.length - 1], -1);
        //输入: nums1 = [2,4], nums2 = [1,2,3,4].
// * 输出: [3,-1]
        for(int i = nums2.length - 2; i >=0; i--){
            if(nums2[i] < nums2[i+1]){
                map.put(nums2[i], nums2[i+1]);
            }else{
                map.put(nums2[i],-1);
                Integer integer = map.get(nums2[i + 1]);
                while (integer!=-1){
                    if (integer==-1) {
                        break;
                    }
                    if (nums2[i]< integer) {
                        map.put(nums2[i], integer);
                        break;
                    }
                    integer = map.get(integer);
                }
            }
        }
        int[] res = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++){
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}